//
// Created by REEJI2219 on 2024-09-18.
//
#include <iostream>
#include <queue>
#include <climits>
using namespace std;
class SymmetricMatrixGraph {

public:
    int v_count;//顶点个数
    int *array;
    bool *visitArray;
    std::queue<int> visitQueue;
    int *distancesArray;
    int *pNodeArray;
    SymmetricMatrixGraph(int v_count) {
        this->v_count = v_count;
        int size = v_count*(v_count+1)/2;
        array = new int[size];
        visitArray=new bool[v_count];
        for(int i=0;i<v_count;i++) {
            visitArray[i]=false;
        }
        //最短距离
        distancesArray = new int[v_count];
        pNodeArray = new int[v_count];
        for(int i=0;i<v_count;i++) {
            distancesArray[i]=INT_MAX;
            pNodeArray[i]=-1;
        }


    }
    int index(int i,int j) {
        if(i>j) {
            return  i*(i+1)/2+j;
        }else {
            return j*(j+1)/2+i;
        }
    }
    void addEdge(int i,int j) {
        array[index(i,j)]=1;
    }
    bool hasEdge(int i,int j) {
        return array[index(i,j)]==1;
    }
    void print() {
        for(int i=0;i<v_count;i++) {
            for(int j=0;j<=i;j++) {
                printf("%d ",array[index(i,j)]);
            }
            printf("\n");
        }
    }

    /**
     * 广度优先遍历
     */
    void BFS() {
        for(int i=0;i<v_count;i++) {
            bfsVisit(i);
        }
    }
    void bfsByIndex(int start) {
        bfsVisit(start);
        printf("\n源点距离: ");
        for(int i=0;i<v_count;i++) {
            printf("%d ",distancesArray[i]);
        }
        printf("\n父亲节点: ");
        for(int i=0;i<v_count;i++) {
            printf("%d ",pNodeArray[i]);
        }
    }

    /**
     * 深度优先遍历
     */
    void DFS() {
        for(int i=0;i<v_count;i++) {
            dfsVisit(i);
        }

    }

    void dfsVisit(int i) {
        if(visitArray[i]) {
            return;
        }
        //当前节点标记为已遍历
        visitArray[i]=true;
        printf("%d ",i);
        for (int j=0;j<v_count;j++) {
            if(array[index(i,j)]==1 && !visitArray[j]) {
                dfsVisit(j);
            }
        }
    }
    void bfsVisit(int i) {
        if(visitArray[i]) {
            return;
        }
        //当前节点标记为已遍历
        visitArray[i]=true;
        printf("%d ",i);
        //作为父节点入队
        visitQueue.push(i);
        distancesArray[i]=0;
        while (!visitQueue.empty()) {
            //父亲节点
            int index_i = visitQueue.front();
            visitQueue.pop();
            for(int j=0;j<v_count;j++) {
                if(array[index(index_i,j)]==1 && !visitArray[j]) {
                    //j为当前节点
                    printf("%d ",j);
                    //距离为父亲距离+1
                    distancesArray[j]=distancesArray[index_i]+1;
                    //记录父亲节点
                    pNodeArray[j]=index_i;
                    visitArray[j]=true;
                    //作为父节点入队
                    visitQueue.push(j);
                }
            }
        }
    }
    void allPrint() {
        for(int i=0;i<v_count;i++) {
            for(int j=0;j<v_count;j++) {
                printf("%d ",array[index(i,j)]);
            }
            printf("\n");
        }
    }
};
class Node {
public:
    int data;
    int cal;
    int row;
    Node *next;
    Node(int i,int j) {
        this->cal=i;
        this->row=j;
        data=0;
        next=nullptr;
    }
};
class MatrixGraph{
public:
    int v_count;
    Node **array;
    bool *visitArray;
    std::queue<int> visitQueue;
    MatrixGraph(int v_count) {
        this->v_count=v_count;
        array = new Node*[v_count];
        visitArray=new bool[v_count];
        // for(int i=0;i<v_count;i++) {
        //     visitArray[i]=false;
        // }
    }
    void transSymmetricToMatrixGraph(SymmetricMatrixGraph *symmetric_matrix_graph) {
        for(int i=0;i<v_count;i++) {
            for(int j=0;j<=v_count;j++) {
                int index = symmetric_matrix_graph->index(i,j);
                int resultValue = symmetric_matrix_graph->array[index];
                // printf("i:%d j:%d index:%d  index_value:%d \n",i,j ,index,resultValue);
                if(resultValue==1) {
                       addEdge(i,j,1);
                }
            }
        }
    }
    void BFS() {
        for (int i=0;i<v_count;i++) {
            bfsVisit(i);
        }
    }
    void DFS() {
        for (int i=0;i<v_count;i++) {
            dfsVisit(i);
        }
    }
    void dfsVisit(int i) {
        if(visitArray[i]) {
            return;
        }
        visitArray[i]=true;
        printf("%d ",i);
        Node *node = array[i];
        while (node!=nullptr) {
            dfsVisit(node->row);
            node = node->next;
        }
    }
    void bfsVisit(int i) {
        if(visitArray[i]) {
            return;
        }
        visitArray[i]=true;
        printf("%d ",i);
        Node *node = array[i];
        while (node!=nullptr) {
            visitQueue.push(node->row);
            node = node->next;
        }
        while (!visitQueue.empty()) {
            int index = visitQueue.front();
            visitQueue.pop();
            bfsVisit(index);
        }
    }
    /**
     * 按列做层级遍历
     * @param i 所在行
     * @param j 所在列
     * @param data
     */
    void addEdge(int i,int j,int data) {
        Node *node = new Node(i,j);
        node->data = data;
        Node *header = array[i];
        if(header==nullptr) {
            array[i]= node;
        }else {
            if(header->row>node->row) {
                node->next = header;
                array[i]= node;
            }else {
                while(header->row<node->row && header->next!=nullptr && header->next->row<node->row) {
                    header =header->next;
                }
                node->next = header->next;
                header->next = node;
            }
        }
    }
    void print() {
        for(int i=0;i<v_count;i++) {
            Node *header = array[i];
            printf(" %d %d %d |",header->cal,header->row,header->data);
            while (header->next!=nullptr) {
                header = header->next;
                printf(" %d %d %d |",header->cal,header->row,header->data);
            }
           printf("\n");
        }
    }

};

// int main(int argc, char *argv[]) {
//     SymmetricMatrixGraph *symmetric_matrix_graph =new SymmetricMatrixGraph(8);
//     symmetric_matrix_graph->addEdge(4,0);
//     symmetric_matrix_graph->addEdge(0,1);
//     symmetric_matrix_graph->addEdge(1,5);
//     symmetric_matrix_graph->addEdge(5,2);
//     symmetric_matrix_graph->addEdge(5,6);
//     symmetric_matrix_graph->addEdge(2,6);
//     symmetric_matrix_graph->addEdge(2,3);
//     symmetric_matrix_graph->addEdge(6,3);
//     symmetric_matrix_graph->addEdge(6,7);
//     symmetric_matrix_graph->addEdge(3,7);
//     symmetric_matrix_graph->print();
//     printf("-----------------------\n");
//     symmetric_matrix_graph->allPrint();
//     printf("-----------------------\n");
//     // symmetric_matrix_graph->BFS();
//     // printf("-----------------------\n");
//     // symmetric_matrix_graph->DFS();
//     // printf("\n-----------------------\n");
//     symmetric_matrix_graph->bfsByIndex(1);
//     // MatrixGraph *matrix_graph = new MatrixGraph(symmetric_matrix_graph->v_count);
//     // matrix_graph->transSymmetricToMatrixGraph(symmetric_matrix_graph);
//     // // matrix_graph->print();
//     // matrix_graph->BFS();
//     // matrix_graph->DFS();
// }
